public class Leetcode {
}

//leetcode:10:正则表达式匹配
class Solution1 {
    public boolean isMatch(String ss, String pp) {
        int m = ss.length() , n = pp.length();
        //在字符串前加上一个空格，便于使用
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //创建一个dp表，表示p中0~j的所有子串都能完全匹配s中0~i的所有子串
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        //注意：如果我们要让*进行匹配，那么我们*前面必须有一个字符
        //所以我们从下标为2的元素遍历，每次隔一个得到一个，如果得到的元素为*，那么当s为空串的时候，就可以进行匹配，但如果不为*，那么后边就无法匹配
        for(int j = 2; j <= n; j += 2){
            if(p[j] == '*'){
                dp[0][j] = true;
            }else{
                break;
            }
        }


        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果j位置为*，且匹配0个字符那么就要判断除*和它前面的字符外，p中0~j-2位置的所有子串是否能完全匹配s中0~i的所有子串，如果*匹配多个字符同时前面的字符为‘.’或者p[j-1]与s[i]的字符相同就去判断，刨除匹配的多个字符外p中的0~j-2的子串是否能完全匹配s中剩余的字符的子串是否能够完全匹配
                if(p[j] == '*'){
                    //dp[i-1][j] = dp[i-1][j-2] || dp[i-2][j-2] || dp[i-3][j-2]........
                    dp[i][j] = dp[i][j-2] || (p[j-1] == '.' || p[j-1] == s[i]) && dp[i-1][j];
                }else{
                    //如果不为*，就要判断此时j位置的字符为‘.’还是与i位置的字符相同，如果相同就要去判断p中的0~j-1的子串是否能完全匹配s中0~i-1的所有子串
                    dp[i][j] = (p[j] == '.' || p[j] == s[i]) && dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }
}

//leetcode:97:交错字符串
class Solution2 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length() , n = s2.length();
        //先判断这两个字符串加到一起后是否能够得到长度为s3的字符串
        if(m + n != s3.length()) return false;
        //将每个字符串都加上一个空格方便后续取元素
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        //创建一个dp表，表示s1字符串中1~i位置的字符串和s2中1~j位置的字符串是否能够完全拼成s3中1~i+j区间的字符串
        boolean[][] dp = new boolean[m+1][n+1];
        //如果都为空串就代表能够拼成s3的空串
        dp[0][0] = true;

        //如果s1为空串，且j位置的元素等于s3中j位置的元素，就代表此时这个区间能够拼成，如果不等就代表后边都不能拼成s3
        for(int j = 1; j <= n; j++){
            if(s2.charAt(j) == s3.charAt(j)){
                dp[0][j] = true;
            }else{
                break;
            }
        }

        //如果s2为空串，且i位置的元素等于s3中i位置的元素，就代表此时这个区间能够拼成，如果不等就代表后边都不能拼成s3
        for(int i = 1; i <= m; i++){
            if(s1.charAt(i) == s3.charAt(i)){
                dp[i][0] = true;
            }else{
                break;
            }
        }


        //都不为空串，就要判断此时s3中i+j位置的元素是与s1中i位置的元素相同还是与s2中j位置的元素相同
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果与s1相同，就要判断s1字符串中1~i-1位置的字符串和s2中1~j位置的字符串是否能够完全拼成s3中1~i-1+j区间的字符串
                //如果与s2相同，就要判断s1字符串中1~i位置的字符串和s2中1~j-1位置的字符串是否能够完全拼成s3中1~i+j-1区间的字符串
                //如果有一个可以拼成，就代表s1字符串中1~i位置的字符串和s2中1~j位置的字符串能够完全拼成s3中1~i+j区间的字符串
                dp[i][j] = (s1.charAt(i) == s3.charAt(i+j) && dp[i-1][j]) || (s2.charAt(j) == s3.charAt(i+j) && dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
}